package com.leetcode.partition5;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/11/24 9:08
 */
public class LC423从英文中重建数字 {

    private static final String[] numberWords = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"};
    private static final int[] numbers = {0, 8, 6, 3, 2, 7, 5, 9, 4, 1};

    public static String originalDigits(String s) {
        /*
        可以先对 s 进行词频统计，然后根据「英文单词中的字符唯一性」确定构建的顺序，最后再对答案进行排序即可。
        具体的，zero 中的 z 在其余所有单词中都没出现过，我们可以先统计 zero 的出现次数，并构建 0；然后观察剩余数字，其中 eight 中的 g 具有唯一性，
        构建 8；再发现 six 中的 x 具有唯一性，构建 6；发现 three 中的 h 具有唯一性（利用在此之前 eight 已经被删除干净，词频中仅存在 three 对应的
        h)，构建 3 ...
        最终可以确定一个可行的构建序列为 0, 8, 6, 3, 2, 7, 5, 9, 4, 1
         */
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
        StringBuilder answer = new StringBuilder();
        for (int number : numbers) {
            //k统计当前单词的最低字符的出现词频
            int k = Integer.MAX_VALUE;
            for (char c : numberWords[number].toCharArray()) k = Math.min(k, count[c - 'a']);
            //以最低词频字符减去当前单词的哈希表
            for (char c : numberWords[number].toCharArray()) count[c - 'a'] -= k;
            while (k-- > 0) answer.append(number);
        }
        char[] ans = answer.toString().toCharArray();
        Arrays.sort(ans);
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        String s = "zeroonetwothreefourfivesixseveneightnine";
        System.out.println(originalDigits(s));
    }
}
